package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 *
 * https://leetcode.cn/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/description
 * ```
 * 1379. 找出克隆二叉树中的相同节点
 *
 * 给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。
 * 其中，克隆树 cloned 是原始树 original 的一个 副本 。
 * 请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。
 * 注意：你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。
 *
 *
 *
 * 示例 1:
 * 输入: tree = [7,4,3,null,null,6,19], target = 3
 * 输出: 3
 * 解释: 上图画出了树 original 和 cloned。target 节点在树 original 中，用绿色标记。答案是树 cloned 中的黄颜色的节点（其他示例类似）。
 *
 * 示例 2:
 * 输入: tree = [7], target =  7
 * 输出: 7
 *
 * 示例 3:
 * 输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
 * 输出: 4
 *
 *
 * 提示：
 * 树中节点的数量范围为 [1, 104] 。
 * 同一棵树中，没有值相同的节点。
 * target 节点是树 original 中的一个节点，并且不会是 null 。
 * ```
 */
class leetcode_1379 {
    @Test
    fun test_2() {
        val original: TreeNode = TreeNode(7)
        val cloned: TreeNode = TreeNode(7)
        val target: TreeNode = TreeNode(7)
        val actual = getTargetCopy(original, cloned, target)
        val expected = cloned
        Assert.assertEquals(expected, actual)
    }


    /**
     * 题型：二叉树的任何一种遍历方式。
     *
     * 思路：因为是克隆树，两个树是一样的，original 没有用，此题出的有点废柴。
     * 遍历树时，若已经得到了目标值，则停止递归。 若没有得到，当判断节点与target相等时，记录当前节点为目标值。
     *
     * 空间复杂度：O（1）
     * 时间复杂度：O（N）
     *
     */
    private var result: TreeNode? = null
    private fun getTargetCopy(original: TreeNode?, cloned: TreeNode?, target: TreeNode): TreeNode? {
        find(cloned, target)
        return result
    }

    private fun find(cloned: TreeNode?, target: TreeNode) {
        // 1 确认函数参数以及返回值
        // 2 确定终止条件
        if (null != result) {
            return
        }
        // 3 确定单层递归的处理逻辑：前序遍历
        if (null != cloned) {
            if (null == result) {
                if (cloned.`val` === target.`val`) {
                    result = cloned
                    return
                }
            }
            // 左
            find(cloned.left, target)

            // 右
            find(cloned.right, target)
        }
    }
}

